//
// Created by DP on 2025/9/3.
//
#include <algorithm>
#include <iostream>
#include <sstream>
#include <stack>
#include <vector>
#include <set>
#include <map>
using namespace std;
#define ll long long


//https://codefun2000.com/p/P2385 注意循环处理
void func1() {
    ll x;
    vector<ll> stk(10010);
    int top=0;
    while (scanf("%lld", &x) != EOF) {
        while (true) {
            bool flag = false;
            ll tmp=0;
            for (int i=top;i&&top;--i) {
                tmp+=stk[i];
                if (tmp==x) {
                    x+=tmp;
                    top=i-1;
                    flag=true;
                    break;
                }
            }
            if (flag==false) {
                break;
            }

        }
        stk[++top]=x;
    }
    while (top>0) {
        cout<<stk[top--]<<" ";
    }
}
//对于multiset的妙用 能够维持自定义顺序
void func2() {
    int q ;
    cin >> q;
    getchar();
    vector<string> cangku;
    std::multiset<string> ms;
    int minidx =0;
    while (q--) {
        string line;
        getline(cin, line);
        stringstream ss(line);
        string token;
        getline(ss, token,' ');
        if (token == "in") {
            string s;
            getline(ss, s);
            cangku.push_back(s);
            ms.insert(s);
        }else if (token == "out") {
            string s;
            if (cangku.size()==0) {
                cout<<"EMPTY"<<endl;
                continue;
            }
            s= cangku.back();
            cangku.pop_back();
            ms.erase(ms.find(s));
            cout<<s<<endl;
        }else if (token == "count") {
            cout<<ms.size()<<endl;
        }else {
            //check
            if (ms.size() == 0) {
                cout<<"EMPTY"<<endl;
            }else {
                cout<<*ms.begin()<<endl;
            }
        }
    }
}

//https://codefun2000.com/p/P2337  tong1 注意top的边界条件 同时还有他是累积最后才加入栈的
void func3() {
    vector<ll> stk(10010);
    int top=0;

    ll n;
    while (scanf("%lld",&n)!=EOF) {
        while (1) {
            bool flag=false;
            unsigned ll tmp=0;
            for (int i=top;i&&top;i--) {
                tmp+=stk[i];
                if (tmp==n) {
                    flag=true;
                    top = i-1;
                    n*=2;
                    break;
                }
            }
            if (flag==false) {
                break;
            }
        }
        stk[++top]=n;
    }
    for (int i=top;i>0;i--) {
        cout<<stk[i]<<" ";
    }
}


//逐个输入 然后如果大于3就开始从末尾判断是否能合并
void func4() {
    int n;
    cin>>n;
    vector<char> v;
    for(int i=0;i<n;i++) {
        char c;
        cin>>c;
        v.push_back(c);
        int m=v.size();
        while(m>=3&&v[m-1]==v[m-2]&&v[m-1]==v[m-3]) {
            for (int i=0;i<3;i++) {
                v.pop_back();
            }
            m=v.size();

        }

    }
    int m=v.size();
    if (!m)
        cout<<0<<endl;
    else {
        for (int i=0;i<m;i++) {
            cout<<v[i]<<" ";
        }
    }
}

//https://codefun2000.com/p/P2322 栈计算表达式 + kmp + 内部函数
int func5() {
    string s;
    cin >> s;
    string pp;
    cin>>pp;
    //处理表达式
    stack<pair<int,string>> st;
    int num=0;
    string res="";

    for (auto c : s) {
        if (isdigit(c)) {
            num=num*10+(c-'0');
        }else if (c=='(') {
            st.push(make_pair(num,res));
            num=0;
            res="";
        }else if (c==')') {
            int n=st.top().first;
            string a=st.top().second;
            st.pop();
            if (n*res.size()+a.size()>pp.size()) {
                cout<<"!"<<endl;
                return 0;
            }
            for (int  i=0;i<n;i++) {
                a+=res;
            }
            res = a;

        }else {
            res+=c;
            if (res.size()>pp.size()) {
                cout<<"!"<<endl;
                return 0;
            }
        }
    }
    // cout<<res<<endl;

    //kmp
    auto check =[](char a,char b) -> bool {
        if (b=='A'&&isalpha(a)) return true;
        if (b=='N'&&isdigit(a)) return true;
        return false;
    };
    //构建next
    //模式串
    string t=res;
    vector<int> next;
    next.push_back(0);

    for (int i=1,j=0;i<t.length();i++) {
        while (j>0&&t[j]!=t[i]) {
            j=next[j-1];
        }
        if (t[i]==t[j]) {
            j++;
        }
        next.push_back(j);
    }

    //匹配 i为pp j为t
    for (int i=0,j=0;i<pp.size();i++) {
        while (j>0&&!check(pp[i],t[j])) {
            j=next[j-1];
        }
        if (check(pp[i],t[j])) {
            j++;
        }
        if (j==t.size()) {
            cout<<pp.substr(i-t.size()+1,t.size())<<endl;
            return 0;
        }
    }
    cout<<"!"<<endl;
    return 0;

}


//https://codefun2000.com/p/P2312 。 栈的模拟
int func6() {
    int n;
    stack<int> s;
    map<int,int> mp;
    vector<int> ans;
    while (cin >> n) {
        if (s.empty()) {
            s.push(n);
            mp[n]++;
        }else if (mp[n]<=0) {
            s.push(n);
            mp[n]++;
        }else {
            while (s.empty()!=true&&s.top()!=n) {
                ans.push_back(s.top());
                mp[s.top()]--;
                s.pop();

            }
            ans.push_back(n);
        }
    }
    for (auto it = ans.begin(); it != ans.end(); it++) {
        cout << *it <<" ";
    }
    while (s.empty()!=true) {
        cout<<s.top()<<" ";
        s.pop();
    }
    return 0;
}

//https://codefun2000.com/p/P2304  模拟栈
int func7() {
    string s;
    cin >> s;
    string cd;
    cin >> cd;
    cin>>cd;
    stack<string> path;
    stringstream ss(s);
    string file;
    int big =0;
    while (getline(ss, file,'/')) {
        if (file != "") {
            path.push(file);
            big=max((int)path.size(),big);
        }
    }
    // while (!path.empty()) {
    //     cout << path.top() << endl;
    //     path.pop();
    // }
    //cout<<cd<<endl;

    ss.clear();
    stringstream ss2(cd);
    stack<string> relpath;

    while (getline(ss2, file,'/')) {
        if (file != "") {
            if (file == ".") {
                continue;
            }else if (file == "..") {
                path.pop();
            }else  {
                path.push(file);
                big=max((int)path.size(),big);
            }
        }
    }
    vector<string >ans;
    while (!path.empty()) {
        ans.push_back(path.top());
        path.pop();
    }
    for (int i=ans.size()-1;i>=0;i--) {
        cout<<"/"<<ans[i];
    }
    cout<<endl;
    // cout<<ans.size()<<endl;
    cout<<big<<endl;
    return 0;
}